package 每日一题;

import com.alibaba.fastjson.JSON;
import javafx.util.Pair;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-05-20
 **/

public class No692前K个高频单词 {

    /**
     * 给一非空的单词列表，返回前 k 个出现次数最多的单词。
     * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
     *
     * 示例 1：
     * 输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
     * 输出: ["i", "love"]
     * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
     *     注意，按字母顺序 "i" 在 "love" 之前。
     * 示例 2：
     * 输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
     * 输出: ["the", "is", "sunny", "day"]
     * 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
     *     出现次数依次为 4, 3, 2 和 1 次。
     * 注意：
     * 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
     * 输入的单词均由小写字母组成。
     *  
     * 扩展练习：
     * 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
     */

    private static class Tree{

        private Character val;
        public int count=0;
        private Map<Character,Tree> next;
        public String value;

        public Tree(Character val) {
            this.val = val;
            this.next = new HashMap<>();
        }

        public Tree getNext(Character c) {
            if(next.get(c)==null){
                next.put(c,new Tree(c));
            }
            return next.get(c);
        }

    }

    public List<String> topKFrequent(String[] words, int k) {

        Tree root=new Tree('-');

        for (String word : words) {

            char[] arr = word.toCharArray();

            Tree cur=root;

            for (int i = 0; i < arr.length-1; i++) {
                cur= cur.getNext(arr[i]);
            }

            Tree next = cur.getNext(arr[arr.length - 1]);
            next.count++;
            next.value=word;

        }

        PriorityQueue<Pair<Integer,String>> priorityQueue=new PriorityQueue<>(k,(o1,o2)->{
            //在前的则是当前队列中最小的
            if(o1.getKey().equals(o2.getKey())){
                //相同频率,则字母序列大的在前
                return o2.getValue().compareTo(o1.getValue());
            }
            //频率小的在前
            return o1.getKey()-o2.getKey();
        });
        dfs(root,priorityQueue,k);

        List<String> result=new ArrayList<>();

        while (!priorityQueue.isEmpty()){
            result.add(priorityQueue.poll().getValue());
        }

        Collections.reverse(result);

        return result;
    }

    private void dfs(Tree tree,PriorityQueue<Pair<Integer,String>> priorityQueue,int k) {

        Map<Character,Tree> map=tree.next;
        for (Map.Entry<Character, Tree> entry : map.entrySet()) {
            Tree value = entry.getValue();
            if(value.count!=0){

                if(priorityQueue.size()<k){
                    priorityQueue.add(new Pair<>(value.count,value.value));
                }else{
                    //与顶部进行比较
                    Pair<Integer, String> pair = priorityQueue.peek();
                    if(pair.getKey()<value.count){
                        //超越
                        priorityQueue.poll();
                        priorityQueue.add(new Pair<>(value.count,value.value));
                    } else if(pair.getKey()==value.count&&pair.getValue().compareTo(value.value)>0){
                        //里面的value顺序小,超越
                        priorityQueue.poll();
                        priorityQueue.add(new Pair<>(value.count,value.value));
                    }
                }

            }
            dfs(entry.getValue(),priorityQueue,k);
        }

    }

    public static void main(String[] args) {
        No692前K个高频单词 n=new No692前K个高频单词();
        String[] arr={"i", "love", "leetcode", "i", "love", "coding"};
        List<String> result = n.topKFrequent(arr, 2);
        System.out.println(JSON.toJSONString(result));
    }

}
